package com.lw.leetcode.arr.c;

import java.util.Arrays;

/**
 * Created with IntelliJ IDEA.
 * 面试题 17.19. 消失的两个数字
 *
 * @author liw
 * @version 1.0
 * @date 2022/9/26 11:10
 */
public class MissingTwo {

    public static void main(String[] args) {
        MissingTwo test = new MissingTwo();

        // 1, 4
//        int[] arr = {3, 2};

        // 2, 3
//        int[] arr = {1};

        // 1, 2
        int[] arr = {1,4};

        // 1, 3
//        int[] arr = {2};

        int[] ints = test.missingTwo(arr);
        System.out.println(Arrays.toString(ints));
    }

    public int[] missingTwo(int[] nums) {
        int length = nums.length;

        int[] arr = new int[2];
        int a = -1;
        int b = -1;
        for (int i = 0; i < length; i++) {
            if (nums[i] == -1 || nums[i] == i + 1) {
                continue;
            }
            int index = nums[i] - 1;
            nums[i] = -1;
            while (true) {
                if (index >= length) {
                    if (a == -1) {
                        a = index;
                    } else {
                        b = index;
                    }
                    break;
                }
                int num = nums[index];
                nums[index] = index + 1;
                if (num == -1) {
                    break;
                }
                index = num - 1;
            }
        }
        int count = 0;

        for (int i = 0; i < length; i++) {
            if (nums[i] == -1) {
                arr[count] = i + 1;
                count++;
            }
        }
        if (count == 0) {
            arr[0] = length + 1;
            arr[1] = length + 2;
        } else if (count == 1) {
            if (a == length + 1 || b == length + 1) {
                arr[1] = length + 1;
            } else {
                arr[1] = length + 2;
            }
        }

//        System.out.println(Arrays.toString(nums));
        return arr;

    }
}
